package dynProg.solvers;

import dynProg.Solver;
/**
 * 
 * @author Stephan Veenstra
 *	@version 1.0
 */

public class BottomUpSolver implements Solver {

	boolean[][] matrix;
	
	private void printMatrix()
	{
		if(matrix != null)
		{
			for(boolean[] i : matrix)
			{
				for(boolean j : i)
					System.out.print((j ? 'Y':'N') + " ");
				System.out.println();
			}
			
		}
	}
	
	@Override
	public boolean solve(int[] numbers, int sum) {

		if(numbers.length == 0 && sum == 0)
			return true;

		matrix = new boolean[numbers.length][sum+1];
		
		for(int i = 0; i < numbers.length;i++)
		{
			int num = numbers[i];
			if(i > 0)
				for(int j = matrix[i].length-1 ; j > 0 ; j--)
				{
					if(matrix[i-1][j])
					{
						matrix[i][j] = true;
						if(j+num <= sum)
							matrix[i][j+num] = true;
						
						if(matrix[i][sum])
							return true;
					}
				}
			matrix[i][num] = true; // Don't forget the number itself
		}
		printMatrix();
		return false;
	}

}
